import collections


class Solution:

    def calc_rc(self, node_index, n):
        row = n - (node_index - 1) // n - 1
        col = (node_index - 1) % n
        if n % 2 == 1:
            if row % 2 == 1:
                col = n - 1 - col
        else:
            if row % 2 == 0:
                col = n - 1 - col
        return row, col


    def snakesAndLadders(self, board) -> int:
        n = len(board)
        helper_queue = collections.deque()
        helper_queue.append((1, 0)) # (到达1号节点, 所需步数）
        visited = [1]

        while helper_queue:
            curr_tuple = helper_queue.popleft()
            for i in range(1, 7): # 掷骰子
                next_node_index = curr_tuple[0] + i
                next_node_row, next_node_col = self.calc_rc(next_node_index, n)
                if board[next_node_row][next_node_col] != -1:
                    next_node_index = board[next_node_row][next_node_col]
                if next_node_index == n * n:
                    return curr_tuple[1] + 1
                if next_node_index not in visited:
                    visited.append(next_node_index)
                    helper_queue.append((next_node_index, curr_tuple[1] + 1))

        return -1



param = [[-1,-1,-1],[-1,9,8],[-1,8,9]]

# 创建 Solution 类的实例
solution = Solution()


# 调用 convert 方法并打印结果
result = solution.snakesAndLadders(param)
print(result)
